/*
 * BigInteger.cpp
 *
 *  Created on: 2010-3-11
 *      Author: liheyuan
 *    Describe: 
 *
 *   Last Date: 2010-3-11
 *   CopyRight: 2010 @ ICT LiHeyuan
 */
#include "../include/BigInteger.h"
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <stdexcept>
using std::ostringstream;
using std::cout;
using std::endl;
using std::runtime_error;

//素数表
static int primes_1000[PRIME_1000_NUMS] =
{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
		73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
		151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
		229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307,
		311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
		397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467,
		479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
		577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
		659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751,
		757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853,
		857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
		953, 967, 971, 977, 983, 991, 997 };

BigInteger::BigInteger()
{
	//将所有的都设置为0
	initZero();
	_maxchunk = 0;
	_sign = true;

}

BigInteger::~BigInteger()
{

}

BigInteger::BigInteger(string str)
{

	//将所有的都设置为0
	initZero();
	_maxchunk = 0;
	_sign = true;

	//Bug of empty str
	if (str.empty())
	{
		return;
	}

	//符号处理
	if (str[0] == '-')
	{
		//负号
		_sign = false;
	}
	else
	{
		//正号
		_sign = true;
	}

	//处理非符号位
	string::iterator itr;
	for (itr = str.begin(); itr != str.end();)
	{
		if (*itr >= '0' && *itr <= '9')
		{
			break;
		}
		else
		{
			itr = str .erase(itr);
		}
	}

	long cnt = 0;
	//注意string和内部表示反向问题
	string::size_type i = 0;
	for (i = str.size() - 1; i >= UNIT_WEI; i -= UNIT_WEI)
	{
		string sub = str.substr(i - UNIT_WEI + 1, UNIT_WEI);
		_data[cnt++] = atoll(sub.c_str());
	}
	//处理最后一个
	if (i >= 0)
	{
		string sub = str.substr(0, i + 1);
		_data[cnt++] = atoll(sub.c_str());
	}

	//对0的额外处理
	if (str == "0")
	{
		this->_sign = true;
	}

	this->_maxchunk = cnt;
}

BigInteger::BigInteger(UNIT_TYPE num)
{
	initZero();
	this->_sign = true;
	this -> _data[0] = num;
	this->_maxchunk = 1;
}

long BigInteger::size() const
{

	return this->toString().size();
}

void BigInteger::initZero()
{
	for (long i = 0; i < UNITS; i++)
	{
		_data[i] = 0;
	}
}

string BigInteger::toString() const
{
	ostringstream ss;
	//输出符号
	if (!_sign)
	{
		ss << "-";
	}

	//如果是0，返回
	if (_maxchunk == 0)
	{
		return "0";
	}

	//最大unit，不补0
	ss << _data[_maxchunk - 1];
	//输出其他unit
	for (long i = _maxchunk - 2; i >= 0; i--)
	{
		ss.fill('0');
		ss.width(UNIT_WEI);
		ss << _data[i];
	}
	return ss.str();
}

int BigInteger::getAt(long i) const
{
	int chunk = i / UNIT_WEI;//计算在第几块
	int left = i % UNIT_WEI;
	UNIT_TYPE tmp = _data[chunk];

	for (long j = 0; j < left; j++)
	{
		tmp /= 10;
	}

	return tmp % 10;
}

BigInteger BigInteger::operator +(const BigInteger & right) const
{
	BigInteger result;

	if (right._sign == _sign)//同号，直接加
	{
		//两个同符号
		result._sign = _sign;

		//开始加法
		long BOUND = std::max(_maxchunk, right._maxchunk);
		//每一UNIT相加
		for (long i = 0; i < BOUND; i++)
		{
			result._data[i] = _data[i] + right._data[i];
		}

		//开始进位
		for (long i = 0; i < BOUND; i++)
		{
			if (result._data[i] > UNIT_MAX_NUM)
			{
				result._data[i + 1]++;
				result._data[i] -= UNIT_JIN_DIFF;
			}
		}

		//设置result的最高有效位
		for (long i = BOUND; i < UNITS; i++)
		{
			if (!result._data[i])
			{
				result._maxchunk = i;
				break;
			}
		}
	}//end if 同号
	else
	{
		//不同符号
		if (!this->_sign && right._sign)//- +
		{
			//把＋转化为-|x|
			BigInteger left(*this);
			left._sign = true;
			result = right.operator -(left);
		}//end if - +
		else//+ -
		{
			result = this->operator -(right.getAbs());
		}//end if + -
	}//end if 不同符号

	return result;
}

BigInteger BigInteger::operator -(const BigInteger &right) const
{
	//根据左右符号，差做判断
	if (!this->_sign && right._sign)//- +
	{
		return this->operator +(right.getNegitive());
	}
	else if (!this->_sign && !right._sign)//- -
	{
		//转化为右减|左边|
		return right.getNegitive().operator -(this->getAbs());
	}
	else if (this->_sign && !right._sign)//+ -
	{
		return this->operator +(right.getAbs());
	}//end if
	else//+ +
	{
		int abs = this->absDiff(right);
		if (abs < 0)//如果左<右，反着减，符号反
		{
			BigInteger result = right.operator -(*this);
			result._sign = false;
			return result;
		}//end if左、右都>0且|左|<|右|
		else//左、右都>0且|左|>|右|
		{
			BigInteger result(*this);

			//Step1:result=this,且从maxChunk-2到0,各从高chunk借位1，注意maxChunk-2才是次高块
			for (long i = result._maxchunk - 2; i >= 0; i--)
			{
				result._data[i] += UNIT_JIN_DIFF;
				result._data[i + 1]--;
			}

			//Step2:分chunk相减，以right的chunk数为标准，多的向上进位
			for (long i = 0; i < right._maxchunk; i++)
			{
				result._data[i] -= right._data[i];
				if (result._data[i] > UNIT_MAX_NUM)//需要进位
				{
					result._data[i] -= UNIT_JIN_DIFF;
					result._data[i + 1]++;
				}
			}

			//Step3:向上进位完
			for (long i = right._maxchunk; i < result._maxchunk; i++)
			{
				if (result._data[i] > UNIT_MAX_NUM)//需要进位
				{
					result._data[i] -= UNIT_JIN_DIFF;
					result._data[i + 1]++;
				}
			}

			//Step3:设定maxChunk
			for (long i = result._maxchunk - 1; i >= 0; i--)
			{
				if (result._data[i] != 0)
				{
					result._maxchunk = i + 1;
					break;
				}
			}

			return result;
		}//end if 左、右都>0且|左|>|右|
	}//end + +
}

BigInteger BigInteger::operator *(int right) const
{
	//用加法模拟乘法3*2=3+3
	BigInteger result;
	for (int i = 0; i < right; i++)
	{
		result = result + *this;
	}
	return result;
}

BigInteger BigInteger::operator *(const BigInteger &right) const
{
	//模拟手动乘法
	BigInteger result;

	//对right的每一位做加法
	const long sizeRight = right.size();

	for (long i = 0; i < sizeRight; i++)
	{
		BigInteger resLine(*this);

		//第一轮：乘法
		const int cur = right.getAt(i);
		for (long j = 0; j < resLine._maxchunk; j++)
		{
			resLine._data[j] *= cur;
		}

		//第二轮：进位
		for (long j = 0; j < resLine._maxchunk; j++)
		{
			if (resLine._data[j] > UNIT_MAX_NUM)
			{
				int jin = (int) (resLine._data[j] / (UNIT_TYPE) UNIT_JIN_DIFF);
				resLine._data[j + 1] += jin;
				resLine._data[j] -= (UNIT_JIN_DIFF * jin);
			}
		}

		//第三轮：maxchunk
		long j;
		for (j = resLine._maxchunk - 1; j < UNIT_MAX_NUM; j++)
		{
			if (resLine._data[j] == 0)
			{
				break;
			}
		}
		resLine._maxchunk = j;

		//第四轮，加零蛋
		string yw = resLine.toString();
		for (long j = 0; j < i; j++)
		{
			yw.append("0");
		}
		resLine = BigInteger(yw);
		//最后：相加
		result = result + resLine;
	}

	return result;
}

BigInteger BigInteger::operator /(const BigInteger &right) const
{
	BigInteger chu, yu;
	this->divAndMod(right, chu, yu);
	return chu;
}

UNIT_TYPE BigInteger::operator %(const UNIT_TYPE &right) const
{
	//快速求模 (a+b)%n = ((a%n)+(b%n))%n ,(a*b)%n = ((a%n)*(b%n))%n
	string numStr = this->toString();
	UNIT_TYPE pre10mod = 0, cur10mod = 0, curmod = 0, mod, arrMod[11];

	//提前计算出0~10%right
	for (int i = 0; i < 11; i++)
	{
		arrMod[i] = i % right;
		//cout << arrMod[i] << endl;
	}

	//第一次运算
	pre10mod = 1 % right;
	mod = (numStr[numStr.size() - 1] - '0') % right;

	//cout << numStr.size() << endl;
	string::reverse_iterator itr = numStr.rbegin();
	itr++;
	for (; itr != numStr.rend(); itr++)
	{
		int wei = ((*itr) - '0');
		//计算当前位的'10'模
		cur10mod = (arrMod[10] * pre10mod) % right;
		//乘以当前位
		curmod = (arrMod[wei] * cur10mod) % right;
		//加上前一位的mod
		mod = ((curmod % right) + (mod % right)) % right;
		pre10mod = cur10mod;
	}

	return mod;
}

BigInteger BigInteger::operator %(const BigInteger &right) const
{
	/*cout << this->toString() << endl << "mod" << endl << right.toString()
	 << endl << endl;*/
	//<right，直接返回
	if (this->operator <(right))
	{
		return *this;
	}

	//快速求模 (a+b)%n = ((a%n)+(b%n))%n ,(a*b)%n = ((a%n)*(b%n))%n
	string numStr = this->toString();
	BigInteger pre10mod = 0, cur10mod = 0, curmod = 0, mod, arrMod[11];

	//提前计算出0~10%right
	for (UNIT_TYPE i = 0; i < 11; i++)
	{
		arrMod[i] = BigInteger(i).slowMod(right);
		//cout << arrMod[i].toString() << endl;
	}

	//第一次运算
	pre10mod = BigInteger(1).slowMod(right);
	mod = arrMod[numStr[numStr.size() - 1] - '0'];

	//cout << numStr.size() << endl;
	string::reverse_iterator itr = numStr.rbegin();
	itr++;
	for (; itr != numStr.rend(); itr++)
	{
		int wei = ((*itr) - '0');
		//计算当前位的'10'模
		cur10mod = (arrMod[10] * pre10mod).slowMod(right);
		//乘以当前位
		curmod = (arrMod[wei] * cur10mod).slowMod(right);
		//加上前一位的mod
		mod = ((curmod.slowMod(right)) + (mod.slowMod(right))).slowMod(right);
		pre10mod = cur10mod;
	}

	return mod;
}

bool BigInteger::operator <(const BigInteger &right) const
{
	int absDiff = this->absDiff(right);

	//为了防止+0和-0需要加入与0的比较
	if (this->isZero() && right.isZero())
	{
		return false;
	}

	//根据符号和绝对值判断
	if (this->_sign && right._sign)//+ +
	{
		if (absDiff < 0)
		{
			return true;
		}
		else
		{
			//>=
			return false;
		}
	}//end + +
	else if (this->_sign && right._sign)//+ -
	{
		//正数总大于负数
		return false;
	}//end + -
	else if (!this->_sign && right._sign)//- +
	{
		//负数总小于正数
		return true;
	}//end - +
	else//- -
	{
		if (absDiff > 0)
		{
			return true;
		}
		else
		{
			//>=
			return false;
		}
	}
}

bool BigInteger::operator >(const BigInteger &right) const
{
	if (this->operator ==(right))//if 判断是否相等
	{
		return false;
	}//end if 相等
	else
	{
		return !(this->operator <(right));
	}//end if 不等
}

bool BigInteger::operator >=(const BigInteger &right) const
{
	if (this->operator ==(right) || this->operator >(right))//if 判断是否相等
	{
		return true;
	}//end if 相等
	else
	{
		return false;
	}//end if 不等
}

bool BigInteger::operator ==(const BigInteger &right) const
{
	//0的bug
	if (this->isZero() && right.isZero())
	{
		return true;
	}

	if (this->_sign != right._sign)//符号不同
	{
		return false;
	}//end 符号不同
	else//符号相同
	{
		int diff = this->absDiff(right);
		//根据绝对值?=0判断
		if (diff == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}//end 符号相同
}

int BigInteger::absDiff(const BigInteger &right) const
{
	if (this->_maxchunk > right._maxchunk)//左块多，所以左大
	{
		return 1;
	}//end if 左块多
	else if (this->_maxchunk < right._maxchunk)//右块多，所以右大
	{
		return -1;
	}//end if 右块多
	else//左右块相等，需要比较每一块
	{
		for (long i = this->_maxchunk - 1; i >= 0; i--)
		{
			if (this->_data[i] != right._data[i])//最大的不一样的chunk差
			{
				if (this->_data[i] > right._data[i])
				{
					return 1;
				}
				else
				{
					return -1;
				}
			}
		}//end for

		//每一chunk都相等
		return 0;
	}//end if chunk数量等
}

BigInteger BigInteger::getAbs() const
{
	BigInteger result(*this);
	result._sign = true;
	return result;
}

void BigInteger::divAndMod(const BigInteger &right, BigInteger &shang,
		BigInteger &yu) const
{
	//注意都要用绝对值处理
	string leftStr = this->getAbs().toString();//转化成string后，最高位在[0]
	BigInteger rightAbs(right.getAbs());
	ostringstream shangSS;
	string::size_type subLen, rightSize;//试商的被除数的长度
	rightSize = rightAbs.size();
	subLen = rightSize;

	//如果商有0，bug
	shangSS.width(1);

	//模拟手除
	while (true)
	{
		//测试是否不用在除了
		BigInteger cur(leftStr);
		if (cur < rightAbs)
		{
			break;
		}

		string sub = leftStr.substr(0, subLen);
		BigInteger subLeft(sub);
		if (subLeft < rightAbs)//被除数当前组<除数，向右再退一个

		{
			subLen++;
			continue;
		}
		else
		{
			//试除法
			int i;
			BigInteger subYu;
			for (i = 0; i <= 9; i++)
			{
				BigInteger subShang(i);
				if ((rightAbs * subShang) > subLeft)
				{
					break;
				}
			}
			i--;//i-1后为sub商
			shangSS << i;
			subYu = subLeft - (rightAbs * BigInteger(i));

			//余数位差>1,商要补0
			long ywDiff = subLeft.size() - subYu.size();
			for (long i = 1; i < ywDiff; i++)
			{
				shangSS << 0;
			}

			//下一组
			leftStr.erase(0, subLen);
			leftStr.insert(0, subYu.toString());
			subLen = rightSize;
		}//end if 可以小除
	}//end 模拟手除法

	//把str结果转化为BigInteger
	shang = BigInteger(shangSS.str());
	yu = BigInteger(leftStr);
	//处理符号
	if (this->_sign == right._sign)
	{
		shang._sign = true;
	}
	else
	{
		shang._sign = false;
	}
}

BigInteger BigInteger::getNegitive() const
{
	BigInteger result(*this);
	result._sign = !result._sign;
	return result;
}

bool BigInteger::isZero() const
{
	if (this->_maxchunk == 0)
	{
		return true;
	}
	else
	{
		//检查每一块是否都是0
		for (long i = 0; i < _maxchunk; i++)
		{
			if (_data[i] != 0)
			{
				return false;
			}
		}
		return true;
	}
}
/*

 BigInteger BigInteger::gcd(const BigInteger &right)
 {
 BigInteger a(*this), b(right), r;
 while (true)
 {
 if (b == 0)
 {
 break;
 }
 r = b;
 b = a % b;
 a = r;
 }
 return a;
 }
 */

bool BigInteger::isProbalePrime()
{
	//先用小素数表过一遍，加速
	if (!smallPrimeTest())
	{
		return false;
	}

	//然后用RabbinMiller测试，小素数表中有2，所以一定是odd
	return millerRabinTest();
}

bool BigInteger::smallPrimeTest()
{
	//测试1～1000的小素数
	for (UNIT_TYPE i = 0; i < PRIME_1000_NUMS; i++)
	{
		if (this->operator %(primes_1000[i]) == 0)
		{
			//如果能和某个素数整除
			return false;
		}
	}
	return true;
}

bool BigInteger::millerRabinTest()
{
	BigInteger ONE(1), TWO(2);

	BigInteger n(*this);
	BigInteger n_1 = (n - ONE);//n_1 = this-1,确保为偶数
	BigInteger s(0), d(n_1);

	//计算n-1=2^s*d
	while (!d.isOdd())//当n_1为偶数时
	{
		d = d.div2();
		s = (s + ONE);
	}
	/*	cout << "n:" << n.toString() << endl;
	 cout << "d:" << d.toString() << endl;*/

	//选取随机整数a,2=<a<=n-2
	for (int i = 0; i < 5; i++)
	{
		//
		BigInteger a = BigInteger(7);
		//BigInteger a = ((BigInteger::getRandomBigInteger(100) % (n - 4)) + TWO);
		//cout << "f" << endl;
		BigInteger x = a.modPow(d, n);
		/*cout << x.toString() << endl;*/

		if (x == ONE || x == n_1)
		{
			continue;
		}
		//for r = 1 .. s − 1
		BigInteger r = ONE;
		bool flag = false;

		for (; r < s; r = r + 1)
		{
			x = x.modPow(TWO, n);
			cout << "x:" << x.toString() << endl;
			if (x == 1)
			{
				return false;
			}
			if (x == n_1)
			{
				//继续下一次测试
				flag = true;
				break;
			}
		}//end for r = 1 .. s − 1

		if (!flag)
		{
			//上面循环都完毕了，不是素数
			return false;
		}
		else
		{
			//继续下一次测试
			continue;
		}
	}//end k times
	return true;
}
BigInteger BigInteger::getRandomBigInteger(unsigned int n)
{
	//random()最多是10位，留出空间，最后几个一位一位生成
	string::size_type BOUNDS = n - 10;
	string numStr;
	srand((unsigned) time(NULL));
	const int BUF_SIZE = 20;
	char buf[BUF_SIZE];

	while (numStr.size() < BOUNDS)
	{
		snprintf(buf, BUF_SIZE, "%d", rand());
		numStr.append(buf);
	}

	while (numStr.size() < n)
	{
		snprintf(buf, BUF_SIZE, "%d", rand() / (RAND_MAX / 10 + 1));
		numStr.append(buf);
	}

	return BigInteger(numStr);
}

BigInteger BigInteger::slowMod(const BigInteger &right) const
{
	//计算this % right
	if (this->operator <(right))
	{
		//小于right，直接返回this
		return *this;
	}
	else
	{
		//开始减法
		BigInteger this2(*this);
		while (this2 >= right)
		{
			this2 = this2 - right;
		}
		return this2;
	}
}

BigInteger BigInteger::modPow(BigInteger e, BigInteger m)
{
	BigInteger r = this->operator %(m);
	BigInteger k = BigInteger(1);
	BigInteger ONE(1);

	while (e > ONE)
	{
		if (e.isOdd())
		{
			k = ((k * r) % m);
		}
		cout << "r:" << r.toString() << endl;
		r = ((r * r) % m);
		e = e.div2();
	}

	return ((r * k) % m);
}

BigInteger BigInteger::div2()
{
	string numStr = this->toString();
	double last = (numStr[numStr.size() - 1] - '0') / 10.0;
	//cout << last * 5 << endl;
	//擦出最后一个，相当于/10,然后*5
	numStr.erase(numStr.size() - 1, 1);
	//cout << numStr << endl;
	numStr = (BigInteger(numStr) * BigInteger(5)).toString();

	BigInteger result(numStr);
	return result + BigInteger((UNIT_TYPE) (last * 5));

}

bool BigInteger::isOdd() const
{
	if (this->_maxchunk == 0)
	{
		return false;
	}
	else
	{
		return ((this->_data[0] % 2) == 1);
	}
}
